Hot melt adhesives based on polyolefins have experienced considerable growth over the last decade, due to their good performance, processability, and, in some cases, cost benefits. Adhesive formulations are disclosed in U.S. Publication 2010/0160497. However, despite their success, there have been occasional pockets of applications where the adhesion to certain “hard-to-bond” substrates has been challenging. Such substrates typically include coated substrates and substrates made from recycled paper. More specifically, the “hard-to-bond” substrates are represented by materials such as clay coatings, wax coatings, polyethylene films and coatings, polypropylene films and coatings, Bi-axially Oriented Polypropylene (BOPP), polyethylene terephthalate (PET), or lacquer-coated Kraft paper. Since these substrates are aesthetically more appealing, they are becoming, increasingly, the substrates of choice for many companies for marketing purposes. There is a need for new adhesive compositions that have improved adhesion to “hard-to-bond” substrates.” These needs have been met by the following invention.